BZOJ1430 小猴打架 < Prufer序列+组合数学 >

Problem

小猴打架

Description

一开始森林里面有只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过次打架之后，整个森林的小猴都会成为好朋友。现在的问题是，总共有多少种不同的打架过程。比如当时，就有六种不同的打架过程。

Input

一个整数，

Output

一行，方案数。

Sample Input

Sample Output

标签：Prufer序列 组合数学

Solution

由可知，一棵有个点的树与一个长为的序列一一对应。那么确定出这样的序列的方案数即可确定最后形成的树的形态。易知这样的序列共有个。再考虑构建树的顺序，即为个元素的全排列数，总数为。故答案为。

Code

#include <bits/stdc++.h>
#define MOD 9999991
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;	lnt ans = 1;
int main() {
    read(n);
    for (int i = 1; i <= n-2; i++) (ans *= 1LL*n) %= MOD; 
    for (int i = 1; i <= n-1; i++) (ans *= 1LL*i) %= MOD;
    return printf("%lld\n", ans), 0;
}